class Solution {
public:
	bool Find(TreeNode* root, TreeNode* x) {
		if (root == nullptr) return false;
		if (root == x) return true;
		return Find(root->left, x) || Find(root->right, x);
	}

	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == nullptr) return nullptr;
		if (root == p || root == q) return root;

		bool PInleft, PInright, QInleft, QInright;
		PInleft = Find(root->left, p);
		PInright = !PInleft;

		QInleft = Find(root->left, q);
		QInright = !QInleft;

		if ((PInleft && QInright) || (QInleft && PInright)) {
			return root;
		}
		else if (PInleft && QInleft)
			return lowestCommonAncestor(root->left, p, q);
		else if (PInright && QInright)
			return lowestCommonAncestor(root->right, p, q);

		return nullptr;
	}
};